package main.Q201_300;

import java.util.*;

public class Q211_220 {
    public static void main(String[] args) {
        System.out.println("Question211：添加与搜索单词-数据结构设计");
        System.out.println("Question212：单词搜索Ⅱ");
        System.out.println("Question213：打家劫舍Ⅱ");
        System.out.println("Question214：");
        System.out.println("Question215：数组中的第K个最大元素");
        System.out.println("Question216：组合总和Ⅲ");
        System.out.println("Question217：存在重复元素");
        System.out.println("Question218：");
        System.out.println("Question219：存在重复元素Ⅱ");
        System.out.println("Question220：存在重复元素Ⅲ");
    }
}

class Question211{
    TreeSet<String> set;
    public Question211() {
        this.set=new TreeSet<>();
    }

    public void addWord(String word) {
        this.set.add(word);
    }

    public boolean search(String word) {
        boolean flag=false;
        for (String s:set){
            if (s.length()!=word.length()) continue;
            else flag=process(word,s);
            if (flag) break;
        }
        return flag;
    }
    public boolean process(String s1,String s2){
        char[] str1=s1.toCharArray(),str2=s2.toCharArray();
        int i=0;
        while (i< str1.length){
            if (str1[i]!=str2[i]&&str1[i]!='.'&&str2[i]!='.')
                return false;
            i++;
        }
        return true;
    }
}

class Question212{
    Set<String> set = new HashSet<>();
    List<String> result = new ArrayList<>();
    char[][] board;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int n, m;
    boolean[][] vis = new boolean[15][15];
    public List<String> findWords(char[][] _board, String[] words) {
        board = _board;
        m = board.length; n = board[0].length;
        for (String w : words) set.add(w);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j] = true;
                sb.append(board[i][j]);
                process(i, j, sb);
                vis[i][j] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return result;
    }
    public void process(int i, int j, StringBuilder sb) {
        if (sb.length() > 10) return ;
        if (set.contains(sb.toString())) {
            result.add(sb.toString());
            set.remove(sb.toString());
        }
        for (int[] d : dirs) {
            int dx = i + d[0], dy = j + d[1];
            if (dx < 0 || dx >= m || dy < 0 || dy >= n) continue;
            if (vis[dx][dy]) continue;
            vis[dx][dy] = true;
            sb.append(board[dx][dy]);
            process(dx, dy, sb);
            vis[dx][dy] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

class Question213{
    public int process(int[] nums,int start,int end){
        int result=-1;
        int[] dp=new int[end+1];
        for (int i=start;i<=end;i++){//最后偷第i家
            int max=0;
            if (i==0||i==1){//前两家自身
                dp[i]=nums[i];
                result=Math.max(result,dp[i]);
                continue;
            }
            for (int j=0;j<i-1;j++){//选取最后偷第i家情况的最优选择
                max=Math.max(max,dp[j]);
            }
            dp[i]=max+nums[i];
            result=Math.max(result,dp[i]);
        }
        return result;
    }
    public int rob(int[] nums) {
        if (nums.length==1) return nums[0];
        else if (nums.length==2) return Math.max(nums[1],nums[0]);
        int a=process(nums,1, nums.length-1);
        int b=process(nums,0, nums.length-2);
        return Math.max(a,b);
    }
}

class Question215{
    public int findKthLargest(int[] nums, int k) {
        int result=0;
        Arrays.sort(nums);
        result=nums[nums.length-k];
//        Deque<Integer> resultQueue=new ArrayDeque<>(),assistQueue=new ArrayDeque<>();//我的NB方法
//        resultQueue.addFirst(nums[0]);
//        for (int i=1;i< nums.length;i++){
//            if (nums[i]>=resultQueue.peekLast()){//当前元素大于等于队尾元素
//                if (resultQueue.size()==k) resultQueue.removeFirst();//当队满，队首出队
//                resultQueue.addLast(nums[i]);//当前元素入队尾
//            }else if (nums[i]<=resultQueue.peekFirst()){//当前元素小于等于队首元素
//                if (resultQueue.size()!=k) resultQueue.addFirst(nums[i]);//当对不满，队首入队
//            }else if (nums[i]<resultQueue.peekLast()&&nums[i]>resultQueue.peekFirst()){//当前元素大于队首元素、小于队尾元素
//                while (resultQueue.peekFirst()<nums[i]){//将队首元素不断移动到辅助队列中，直至队首大于等于当前元素
//                    int temp=resultQueue.pollFirst();
//                    assistQueue.addLast(temp);
//                }
//                resultQueue.addFirst(nums[i]);//当前元素队首入队
//                while (resultQueue.size()!=k&&!assistQueue.isEmpty()){//当辅助队列为空且队满时结束
//                    int temp=assistQueue.pollLast();//将辅助队列中的队尾元素入队首
//                    resultQueue.addFirst(temp);
//                }
//            }
//        }
//        result=resultQueue.pollFirst();//队首即为答案
        return result;
    }
}

class Question216{
    List<List<Integer>> list=new ArrayList<>();
    public void process(int curSum,int curCount,int start,List<Integer> curList){
        if (curSum==0&&curCount==0){
            list.add(curList);
            return;
        }
        for (int i=start;i<=9;i++){
            List<Integer> nowList=new ArrayList<>();
            nowList.addAll(curList);
            nowList.add(i);
            process(curSum-i,curCount-1,i+1,nowList);
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> tempList=new ArrayList<>();
        process(n,k,1,tempList);
        return list;
    }
}

class Question217{
    public boolean containsDuplicate(int[] nums) {
        boolean flag=false;
        Set<Integer> set=new HashSet<>();
        for (int i=0;i< nums.length;i++){
            if (set.contains(nums[i])){
                flag=true;
                break;
            }else set.add(nums[i]);
        }
        return flag;
    }
}

class Question219{
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        boolean flag=false;
        for (int i=0;i< nums.length;i++){
            for (int j=1;j+i< nums.length&&j<=k;j++){
                if (nums[i]==nums[j+i]){
                    flag=true;
                    break;
                }
            }
            if (flag) break;
        }
        return flag;
    }
}

class Question220{
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) valueDiff);
            if (ceiling != null && ceiling <= (long) nums[i] + (long) valueDiff) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= indexDiff) {
                set.remove((long) nums[i - indexDiff]);
            }
        }
        return false;
    }
}